package leetcode_800;

/**
 *@author 周杨
 *BestTimeToBuyAndSellStockWithTransactionFee_714 每次股票交易都要付额外费用 问最大收益
 *describe:典型的动态的规划 因为本次买是依赖前一天的状态 状态只有2种  卖了还是买了  局部解构造全局解 AC 45%
 *2018年10月11日 下午5:51:01
 */
public class BestTimeToBuyAndSellStockWithTransactionFee_714_ {
	/**
	 * describe:贪心思想 每次只要赚钱 就买卖  但是这里有个fee 要尽量保证少次交易
	 * 2018年10月11日 下午3:47:43
	 */
	public int maxProfit1(int[] prices, int fee) {
        int res=0;
        for(int i=1;i<prices.length;++i) {
        	int diff=prices[i]-prices[i-1]-fee;
        	if(diff>0) {
        		res+=diff;
        	}
        }
        return res;
    }
	
	/**
	 * describe:动态规划 
	 * 2018年10月11日 下午5:50:51
	 */
	public int maxProfit(int[] prices, int fee) {
        int dp0=0,dp1=-prices[0];//0是当前没有持有股票的最优解 1是当前持有股票的最优解
        for(int i=1;i<prices.length;++i) {
        	dp0=Math.max(dp0, dp1+prices[i]-fee);
        	dp1=Math.max(dp1,dp0-prices[i]);
        }
        return dp0;
    }
}
